package com.leetcode;

import java.util.Arrays;
import java.util.Scanner;

/**
 * TODO
 *
 * @author lefly
 * @version 1.0
 * @classname No62
 * @description 62. 不同路径
 * @date 2021/1/26 下午4:48
 */
public class No62 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int res = uniquePaths(m,n);
        System.out.println(res);
    }

    public static int uniquePaths(int m, int n) {
        if(m == 0 || n == 0){
            return 0;
        }
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        // 动态规划问题
        // dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        for(int i = 1;i < m;i++){
            for (int j = 0; j < n ; j++) {
                if(j == 0){
                    dp[j] = 1;
                }else{
                    dp[j] += dp[j - 1];
                }
            }
        }
        return dp[n - 1];

    }

}
